package graph.base;

import linear.Queue;

/**
 * 广度优先
 */
public class BreadthFirstSearch {

    private boolean[] marked;
    private int count;
    private Queue<Integer> waitSearch;

    public BreadthFirstSearch(Graph g, int s) {
        marked = new boolean[g.V()];
        waitSearch = new Queue<>();
        bfs(g, s);
    }

    private void bfs(Graph g, int v) {
        marked[v] = true;
        waitSearch.enqueue(v);
        while (!waitSearch.isEmpty()) {
            Integer wait = waitSearch.dequeue();
            for (Integer w : g.adj(wait)) {
                if (!marked[w]) {
                    bfs(g, w);
                }
            }
        }
        count++;
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count() {
        return count;
    }
}
